package com.lihepeng.leecode.tree;

/**
 * 前缀树
 * 多路二叉树
 * 判断节点
 * Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：
 *
 * 指向子节点的指针数组 \textit{children}children。对于本题而言，数组长度为 2626，即小写英文字母的数量。此时 \textit{children}[0]children[0] 对应小写字母 aa，\textit{children}[1]children[1] 对应小写字母 bb，…，\textit{children}[25]children[25] 对应小写字母 zz。
 * 布尔字段 \textit{isEnd}isEnd，表示该节点是否为字符串的结尾。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class Trie {
    /** Initialize your data structure here. */
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie trie = this;
        for (int i =0;i<word.length();i++) {
            char ch  = word.charAt(i);
            int index = ch-'a';
            if (trie.children[index] == null){
                trie.children[index] = new Trie();
            }
            trie = trie.children[index];

        }
        trie.isEnd = true;

    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return true;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return true;
    }
    private Trie searchPrefix(){
        return null;
    }
}
